import java.util.*;

/**
 * 1207. 独一无二的出现次数
 * https://leetcode-cn.com/problems/unique-number-of-occurrences/
 */
public class Solutions_1207 {
    public static void main(String[] args) {
//        int[] arr = {1, 2, 2, 1, 1, 3};  // output: true
//        int[] arr = {1, 2};  // output: false
        int[] arr = {-3, 0, 1, -3, 1, 1, 1, -3, 10, 0};  // output: true

        boolean result = uniqueOccurrences(arr);
        System.out.println(result);
    }

    /**
     * 解法二：排序 + 哈希表
     */
    public static boolean uniqueOccurrences(int[] arr) {
        // 数组长度不大，可以先排序
        Arrays.sort(arr);
        Set<Integer> set = new HashSet<>();
        int count = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                // 与前一元素相同，出现次数加 1
                count ++;
            } else {
                // arr[i - 1] 的数字遍历完毕，共出现了 count 个
                if (set.contains(count)) {
                    return false;
                }
                // 出现次数记录到 set 中
                set.add(count);
                // 重置出现次数
                count = 1;
            }
        }
        // 判断结束后，还需要判断最后一个元素共出现的次数
        if (set.contains(count)) {
            return false;
        }
        return true;
    }

    /**
     * 解法一：哈希数组
     */
    public static boolean uniqueOccurrences2(int[] arr) {
        // map[1000] = 2，说明元素 0 在 arr 数组中出现 2 次
        int[] map = new int[2 * 1000 + 1];
        for (int num : arr) {
            // 元素可能是负数，最大负数是 -1000，那么加 1000 成为 0
            map[num + 1000] ++;
        }
        // countMap[100] = true，说明已经有一个元素出现过 100 次
        // 长度定义为 1001，因为数组长度最多为 1000，即极端情况下，一个元素会出现 1000 次
        boolean[] countMap = new boolean[1001];
        for (int i = 0; i < map.length; i++) {
            if (map[i] > 0) {
                if (countMap[map[i]]) {
                    // 存在两个数的出现次数相同，return false
                    return false;
                }
                // 标记次数 map[i] 已经出现过
                countMap[map[i]] = true;
            }
        }
        return true;
    }
}
